package com.wang.violentrecursion;

/**
 * @Author: along
 * @Create: 2021/5/6
 * @Description:
 */
public class Demo10_CoinsWay {
    //范围尝试
    public static int ways1(int arr[], int aim) {
        if(arr == null || arr.length == 0 || aim < 0) {
            return 0;
        }
        return process1(arr, 0, aim);
    }
    //可以自由使用arr[index.....]所有的面值，每种面值课使用任意张
    public static int process1(int[] arr, int index, int rest) {
        //rest >=0
        if(index == arr.length) {//没有硬币可以选择
            return rest == 0 ? 1 : 0;//若剩余的钱也为0 那么刚好达到目标 存在一种方法 反之 无法解决 返回0
        }
        int ways = 0;
        //当前有arr[index]的货币   i 为 使用硬币的个数
        for (int i = 0; i * arr[index] <= rest; i++) {
            //累加子问题得到的方法数累加
            ways += process1(arr, index + 1, rest - (i * arr[index]));
        }
        return ways;
    }
    //记忆化搜索
    public static int ways2(int[] arr, int aim) {
        if(arr == null || arr.length == 0 | aim ==0) {
            return 0;
        }
        int N = arr.length;
        int[][] dp = new int[N + 1][aim + 1];
        //一开始所有的过程都没有计算 设置dp[...][...] = -1
        for (int i = 0; i < dp.length; i++) {
            for (int j = 0; j < dp[0].length; j++) {
                dp[i][j] = -1;
            }
        }
        return process2(arr, 0, aim, dp);
    }

    public static int process2(int[] arr, int index, int rest, int[][] dp ){
        //如果index和rest参数组合，是没算过的， dp[index][rest] = -1;
        //如果index和rest参数组合，是算过的， dp[index][rest] != -1;
        if(dp[index][rest] != -1) {
            return dp[index][rest];//直接取缓存
        }
        if(index == arr.length) {
            dp[index][rest] = rest == 0 ? 1 : 0;
            return  dp[index][rest];
        }
        int ways = 0;
        //当前有arr[index]的货币   i 为 使用硬币的个数
        for (int i = 0; i * arr[index] <= rest; i++) {
            //累加子问题得到的方法数累加
            ways += process2(arr, index + 1, rest - (i * arr[index]), dp);
        }
        dp[index][rest] = ways;//返回前先放入缓存
        return ways;
    }
    //改经典动态规划
    public static int ways3(int[] arr, int aim) {
        if(arr == null || arr.length == 0 | aim ==0) {
            return 0;
        }
        int N = arr.length;
        int[][] dp = new int[N + 1][aim + 1];
        dp[N][0] = 1;//dp[N][1...aim] = 0
        for (int index = N - 1; index >= 0; index--) {
            for (int rest = 0; rest <= aim; rest++) {
                int ways = 0;
                for (int i = 0; i * arr[index] <= rest; i++) {
                    ways += dp[index + 1][rest - (i * arr[index])];
                }
                    dp[index][rest] = ways;
            }
        }
        return dp[0][aim];
    }
    //优化动态规划
    public static int ways4(int[] arr, int aim) {
        if(arr == null || arr.length == 0 | aim ==0) {
            return 0;
        }
        int N = arr.length;
        int[][] dp = new int[N + 1][aim + 1];
        dp[N][0] = 1;//dp[N][1...aim] = 0
        for (int index = N - 1; index >= 0; index--) {
            for (int rest = 0; rest <= aim; rest++) {
                //枚举重复 去重，只要不越界 index，rest位置依赖于index+1，rest和index，rest-arr[index]位置
                dp[index][rest] = dp[index + 1][rest];
                if(rest - arr[index] >= 0 ) {
                    dp[index][rest] += dp[index][rest - arr[index]];
                }
            }
        }
        return dp[0][aim];
    }

    public static void main(String[] args) {
        int[] arr = {5, 20 , 1, 10, 50};
        int aim = 110;
        System.out.println(ways1(arr,aim));
        System.out.println(ways2(arr, aim));
        System.out.println(ways3(arr, aim));
        System.out.println(ways4(arr, aim));
    }
}
